In this paper, we proposed an effective approach for scheduling ofmultiprocessor unit time tasks with chain precedence on to large multiprocessorsystem. The proposed longest chain maximum processor scheduling algorithm isproved to be optimal for uniform chains and monotone(non-increasing/non-decreasing) chains for both splitable and non-splitablemultiprocessor unit time tasks chain. Scheduling arbitrary chains ofnon-splitable multiprocessor unit time tasks is proved to be NP-completeproblem. But scheduling arbitrary chains of splitable multiprocessor unit timetasks is still an open problem to be proved whether it is NP-complete or can besolved in polynomial time. We have used three heuristics (a) maximumcriticality first, (b) longest chain maximum criticality first and (c) longestchain maximum processor first for scheduling of arbitrary chains. Also comparedperformance of all three scheduling heuristics and found out that the proposedlongest chain maximum processor first performs better in most of the cases.
展开▼
